#include <iostream>

class MinHeap
{
private:
    int _max;
    int _count;
    int *_ptr;

public:
    MinHeap(int number)
    {
        _max = number;
        _count = 0;
        _ptr = new int(_max);
    }
    ~MinHeap()
    {
        if (_ptr)
        {

            delete[] _ptr;
            _ptr = nullptr;
        }
    }

    //最小堆，最小值在根节点
    void push(int number)
    {
        if (_count >= _max)
            return;

        _ptr[_count] = number;
        int j = _count;
        while (j > 0)
        {
            int i = (j - 1) / 2; // 计算父节点位置，调整后的数组是从根节点开始，从下到上，从左到右
            if (_ptr[i] <= _ptr[j])
                break;

            std::swap(_ptr[i], _ptr[j]); // 交换值
            j = i;                       // 当前操作节点
        }
        _count++;
    }
    // 从新排堆， 下沉数值
    void pop()
    {
        if (_count < 1)
            return;

        _count--;
        int i = 0, last = _count - 1;
        _ptr[i] = _ptr[_count]; // 交换最后一个和根节点值
        while (i < last)
        {
            int j = 2 * i + 1; // 当前节点下的左子节点
            // 左节点大于右节点
            if (j < last && _ptr[j] > _ptr[j + 1]) // 从根节点开始，自上向下遍历， 从左到右
                j++;
            if (_ptr[i] < _ptr[j])
                break;
            std::swap(_ptr[i], _ptr[j]); // 交换
            i = j;
        }
    }
    int count() { return _count; }
    int *data() { return _ptr; }
};

class MaxHeap
{
private:
    int _max;
    int _count;
    int *_ptr;

public:
    MaxHeap(int number)
    {
        _max = number;
        _count = 0;
        _ptr = new int(_max);
    }
    ~MaxHeap()
    {
        if (_ptr)
        {

            delete[] _ptr;
            _ptr = nullptr;
        }
    }

    void push(int n)
    {
        if (_count >= _max)
            return;
        _ptr[_count] = n;
        int j = _count;
        while (j > 0)
        {
            int i = (j - 1) / 2;    // 父节点
            if (_ptr[i] >= _ptr[j]) // 父节点大于等于子节点
                break;

            std::swap(_ptr[i], _ptr[j]);
            j = i;
        }
        _count++;
    }

    void pop()
    {
        if (_count < 1)
            return;

        _count--;
        int j = 0, last = _count - 1;
        _ptr[j] = _ptr[_count];
        while (j < last)
        {
            // 计算当前节点的左子节点
            int i = j * 2 + 1;
            if (i < last && _ptr[i] < _ptr[i + 1])
                i++;
            if (_ptr[j] > _ptr[i]) // 根节点大于最大的子节点
                break;
            std::swap(_ptr[j], _ptr[i]);
            j = i;
        }
    }
    int count() { return _count; }
    int *data() { return _ptr; }
};

int main(int argc, char const *argv[])
{
    MaxHeap myheap = 256;
    int sample[] = {2, 3, 5, 3, 1, 99, 7, 32};
    for (int i = 0; i < sizeof(sample) / sizeof(int); i++)
    {
        myheap.push(sample[i]);
        for (int k = 0; k < myheap.count(); k++)
        {
            printf("%d ", myheap.data()[k]);
        }
        printf("\n-------------------------\n");
    }
    myheap.pop();
    for (int k = 0; k < myheap.count(); k++)
    {
        printf("%d ", myheap.data()[k]);
    }
    printf("\n-------------------------\n");
    return 0;
}
